package 蓝桥杯算法;

import 栈.ArrayStack;
import 队列.LinkedListQueue;

public class day10 {
    public static void main(String[] args) {
        day10 a=new day10();
        String s="asdaasddd";
        System.out.println( a.removeElement1(s));

    }
    ArrayStack<Integer> stackInt;
    ArrayStack<Integer> stackOut;
    class MyQueue{

        public MyQueue(){
            stackInt= new ArrayStack<>(100);
            stackOut=new ArrayStack<>(100);

        }
        public void push(int x){
            stackInt.push(x);
        }
        public int poo(){
            dumstackIn();//把stackIn内的结果弹出
            return stackOut.pop();
        }
        public int peek(){
            dumstackIn();
            return stackOut.peek();
        }
        public boolean isempty(){
            return stackOut.isEmpty()&&stackInt.isEmpty();
        }
        public void dumstackIn(){
            if(!stackOut.isEmpty()){
                return;
            }//不为空等其空掉再把下面的值放入
            while(!stackInt.isEmpty()){
                stackOut.push(stackInt.pop());
            }
        }
    }
    public boolean isValid(String s){
        ArrayStack<Character> deque=new ArrayStack<>(100);
        char ch;
        for(int i=0;i<s.length();i++){
            ch=s.charAt(i);
            if(ch=='('){
                deque.push(')');
            }
            else if(ch=='{'){
                deque.push('}');
            }
            else if(ch=='['){
                deque.push(']');
            }
            else if(deque.isEmpty()||deque.peek()!=ch){//未匹配玩结果就空了
                return false;
            }
            else {
                deque.pop();
            }
        }
        return deque.isEmpty();//匹配完还不空
    }
    public String removeElement(String s){
        StringBuffer res=new StringBuffer();
        int top=-1;
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(top>0&&res.charAt(top)==ch){
                res.deleteCharAt(top);
                top--;
            }
            else{
                res.append(ch);
                top++;
            }
        }
        return res.toString();
    }
    public String removeElement1(String s){
        char[] ch=s.toCharArray();
        int fast=0;
        int slow=0;
        while(fast<s.length()) {
            ch[slow] = ch[fast];

            if (slow > 0 && ch[slow] == ch[slow - 1]) {
                slow--;
            } else {
                slow++;
            }
            fast++;
        }
        return new String(ch,0,slow);
    }
    public int evalprn(String[] tokens){
        ArrayStack<Integer> stack =new ArrayStack<>(100);
        for(String s: tokens){
            if("+".equals(s)){
                stack.push(stack.pop()+stack.pop());
            }
             else if("-".equals(s)){
                 stack.push(-stack.pop()+stack.pop());
            }
             else if("*".equals(s)){
                 stack.push(stack.pop()*stack.pop());
            }
             else if("/".equals(s)){
                 int temp1=stack.pop();
                 int temp2=stack.pop();
                 stack.push(temp2/temp1);
             }
             else {
                stack.push(Integer.valueOf(s));//取值并且改成数值
            }
        }
        return stack.pop();
    }
    class MyQueue1{
        LinkedListQueue<Integer> deque=new LinkedListQueue<>(100);
        void poll(int value){
            if(!deque.isEmpty()&&deque.peek()<=value){
                deque.poll();
            }
        }
        void add(int value){
            while (!deque.isEmpty()&&deque.peek()<value){
                deque.poll();//把较小的值全部清空
            }
            deque.offer(value);
        }
        int peek(){
            return deque.peek();
        }
    }
    public int [] getMax(int[] nums,int k){
      if(nums.length==1){
          return nums;
      }
      int num=0;
      MyQueue1 myQueue=new MyQueue1();
      int[] res=new int[nums.length-k+1];
      for(int i=0;i<nums.length;i++){
          myQueue.add(nums[i]);
      }
      res[num++]=myQueue.peek();//保留的便是最大值
        for(int i=k;i<nums.length;i++){
            myQueue.poll(nums[i-k]);//移除前面的元素
            myQueue.add(nums[i]);
            res[num++]=myQueue.peek();
        }
      return res;

    }

}
